package com.study.sort;


/**
 * 合并两个有序的数组--指针移动思想
 *
 * @author yyb8152
 * @since 20220826
 **/
public class MegerSort {
    public static void main(String[] args) {
        int[] one = {2, 5, 7, 8};
        int[] two = {1, 3, 9, 10};

        int[] mergeSort = mergeSort(one, two);

        for (int num : mergeSort) {
            System.out.print(num + "-");

        }


    }

    public static int[] mergeSort(int[] one, int[] two) {
        if (one.length == 0 || two.length == 0) {
            return new int[0];
        }
        // 定义One数组的下标（指针）
        int onePoint = 0;
        // 定义two数组的下标（指针）
        int twoPoint = 0;
        // 定义合并后有序的数组
        int[] three = new int[one.length + two.length];
        // 遍历
        for (int i = 0; i < three.length; i++) {
            // 第一种情况：两个指针还分别位于两个数组的起始（或者还在其中）位置,开始往尾部移动
            if (onePoint < one.length && twoPoint < two.length) {
                // 两个数组从起始位置开始比较大小
                if (one[onePoint] > two[twoPoint]) {
                    // 把小的值赋给合并的数组
                    three[i] = two[twoPoint];
                    // 指针往后移动一个位置
                    twoPoint++;
                    // 同理
                } else {
                    three[i] = one[onePoint];
                    onePoint++;
                }

                // 俩数组比较结束。但有的指针还没有移动到尾部
                // 第二种情况：在比较的过程中two数组的指针还没移动到尾部但one数组指针已经到达了尾部（元素已经全部存入合并数组里）
            } else if (twoPoint < two.length) {
                // 把剩余的元素依次填充大合并数组里
                three[i] = two[twoPoint];
                // 指针往后移动一个位置。直到末尾i
                twoPoint++;

                // 同理：one数组的指针还没有移动到尾部
            } else if (onePoint < one.length) {
                three[i] = one[onePoint];
                onePoint++;
            }

        }
        return three;
    }

}
